10515. Степень

По заданным двум неотрицательным числам m и n найти последнюю цифру числа mⁿ в десятичной системе исчисления.

Вход. Содержит менее 100000 строк. Каждая строка содержит два числа m и n, которые меньше 10¹⁰¹. Последняя строка содержит два нуля и не обрабатывается.

Выход. Для каждого теста вывести последнюю цифру числа mⁿ.

Пример входа

2 2

2 5

0 0

Пример выхода

4

2

РЕШЕНИЕ

математика

Анализ алгоритма

Для нахождения последней цифры числа mⁿ достаточно знать последнюю цифру a основания m и две последние цифры степени n. При возведении в степень числа a (a < 10) последняя цифра aⁱ или остается равной a (при a = 0, 1, 5, 6), или повторяется с периодом 2 (при a = 4, 9), или повторяется с периодом 4 (при a = 2, 3, 7, 8). Степень n делится на 4, если число, составленное из ее последних двух цифр, делится на 4.

Построим целочисленный двумерный массив d[10][4], у которого d[a][i mod 4] равно цифре, на которую оканчивается число aⁱ , i > 0. Если последней цифрой основания m является a, а последние две цифры степени n образуют число i, то достаточно вывести значение d[a][i mod 4]. Отдельно следует обработать случай, когда степень равна 0 (i = 0).

Реализация алгоритма

Массив d объявлен ниже. Массивы s1 и s2 содержат соответственно числа m и n.

int d[10][4] = {{0,0,0,0},{1,1,1,1}, {6,2,4,8}, {1,3,9,7},

{6,4,6,4}, {5,5,5,5}, {6,6,6,6}, {1,7,9,3},

{6,8,4,2}, {1,9,1,9}};

char s1[102],s2[102];

Читаем входные числа, пока не встретится m = n = 0. В переменную digit занесем последнюю цифру числа m, в переменную power – последние две цифры числа n. Если степень n равна 0 (длина n равна 1, power = 0), то выводим 1. Иначе печатаем d[digit][power % 4].

while(scanf("%s %s",s1,s2),strcmp(s1,"0") || strcmp(s2,"0"))

{

digit = s1[strlen(s1)-1] - '0';

len2 = strlen(s2);

power = s2[len2-1] - '0';

if (len2 > 1) power += 10*(s2[len2-2] - '0');

if ((len2 == 1) && (power == 0)) printf("1\n");

else printf("%d\n",d[digit][power % 4]);

}